package LeetCode.month01.day12;

public class No45 {
    public static void main(String[] args) {
        int[] arr = new int[] {2,3,1,1,4};
        System.out.println(jump(arr));
    }
    public static int jump(int[] nums) {
        int end = 0;
        int step = 0;
        int rightmax = 0;
        int len = nums.length;
        for (int i = 0; i < len-1; i++) {
            rightmax = Math.max(rightmax,i+nums[i]);
            if(i==end) {
                step++;
                end = rightmax;
            }
        }
        return step;



        //反向查找，依次找到最近能到达边界的顶点
//        int len = nums.length-1;
//        int step = 0;
//        while(len>0){
//            for (int i = 0; i < len; i++) {
//                if(nums[i]+i>=len){
//                    len = i;
//                    step++;
//                    break;
//                }
//            }
//        }
//        return step;
    }
}
